/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

import java.util.ArrayList;
import java.util.List;
/**
 * <p>标题：最大整除子集</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/largest-divisible-subset/
 * </pre>
 * <p>创建日期：2019年12月4日上午11:15:58</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code368LargestDivisibleSubset</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code368LargestDivisibleSubset
{
	public static void main(String[] args)
	{
		/**
		 * 给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

		如果有多个目标子集，返回其中任何一个均可。

		 

		示例 1:

		输入: [1,2,3]
		输出: [1,2] (当然, [1,3] 也正确)
		示例 2:

		输入: [1,2,4,8]
		输出: [1,2,4,8]

		 */
		List<Integer> largestDivisibleSubset = largestDivisibleSubset(new int[] { 2, 5, 4, 8 });
		System.out.println(largestDivisibleSubset);
	}

	/**
	 * TODO 待做完。。。
	 * @param nums
	 * @return
	 */
	public static List<Integer> largestDivisibleSubset(int[] nums)
	{
		int[] dp = new int[nums.length];
		dp[0] = 1;
		int max = 1;
		List<Integer> result = new ArrayList<Integer>();
		for (int i = 1; i < dp.length; i++)
		{
			int maxVal = 0;
			for (int j = 0; j < i; j++)
			{
				if (nums[j] % nums[i] == 0 || nums[i] % nums[j] == 0)
				{
					maxVal = Math.max(maxVal, dp[j]);
				}
			}
			dp[i] = maxVal + 1;
			//			if (dp[i] > max)
			//			{
			//				result.add(i);
			//			}
			max = Math.max(dp[i], max);
		}
		for (int i = 0; i < dp.length; i++)
		{
			System.out.print(dp[i] + "\t");
		}
		System.out.println();
		System.out.println("max:" + max);
		return result;
	}
}
